import java.lang.reflect.GenericDeclaration;

public class Sort {
    // 选择排序
    public static void selectSort(int[] array){
        // write code  here
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap1(array,minIndex,i);
        }
    }


    public static void swap1(int[] array,int minIndex,int i) {
        int tmp = array[minIndex];
        array[minIndex] = array[i];
        array[i] = tmp;
    }

// 堆排序
    public static void heapSort(int[] array){
        // write code  here
        createBigHeap(array);
        int end = array.length - 1;
        while(end > 0) {
            swap2(array,0,end);
            siftDown(array,0,end);
            end --;
        }
    }

    private static void createBigHeap(int[] array) {
        for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {
            siftDown(array,parent, array.length);
        }
    }

    public static void swap2(int[] array,int child,int parent) {
        int tmp = array[child];
        array[child] = array[parent];
        array[parent] = tmp;
    }
    private static void siftDown(int[] array,int parent,int end) {
        int child = 2*parent + 1;
        while(child < end) {
            if(child+1 < end && array[child] < array[child+1]) {
                child ++;
            }
            if(array[child] > array[parent]) {
                swap2(array, child, parent);
                parent = child;
                child = 2*parent +1;
            }else {
                break;
            }

        }
    }





    // 冒泡排序
    public static void bubbleSort(int[] array){
        // write code  here
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if(array[j] > array[j+1]) {
                    swap2(array,j,j+1);
                    flg = true;
                }
            }
            if(!flg) {
                return;
            }
        }
    }

    // 快速
    public static void quickSort(int[] array){
        // write code  here
        quick(array,0,array.length-1);

    }
    private static void quick(int[] array,int start,int end) {
        if(start >= end) return;
        int pivot = parttoin(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);

    }

    private static int parttoin(int[] array,int left,int right) {
        int key = array[left];
        int i = left;
        while(left < right) {
            while(left < right && array[right] >= key) {
                right --;
            }
            while (left < right && array[left] <= key) {
                left ++;
            }
            swap2(array,left,right);
        }
        swap2(array,i,left);
        return left;
    }
}
